package com.godme.structure;

public class RBT {

    RBN root; //根节点

    public static void main(String[] args) {
        RBT rb = new RBT();
        rb.insert(10);//根节点
        rb.insert(5);
        rb.insert(9);
        rb.insert(3);
        rb.insert(6);
        rb.insert(7);
        rb.insert(19);
        rb.insert(32);
        rb.insert(24);
        rb.insert(17);
        rb.list(rb.root);
    }

    public void list(RBN node) {
        if (node == null) return;
        if (node.getLeft() == null && node.getRight() == null) {
            System.out.println(node);
            return;
        }
        System.out.println(node);
        list(node.getLeft());
        list(node.getRight());
    }

    public void insert(int key) {
        RBN node = new RBN(key);
        if (root == null) {
            node.setBlack(true);
            root = node;
            return;
        }
        RBN parent = root;
        RBN son = null;
        if (key <= parent.getKey()) {
            son = parent.getLeft();
        } else {
            son = parent.getRight();
        }
        while (son != null) {
            parent = son;
            if (key <= parent.getKey()) {
                son = parent.getLeft();
            } else {
                son = parent.getRight();
            }
        }
        if (key <= parent.getKey()) {
            parent.setLeft(node);
        } else {
            parent.setRight(node);
        }
        node.setParent(parent);
        banlanceInsert(node);
    }

    private void banlanceInsert(RBN node) {
        RBN father, grandFather;
        while ((father = node.getParent()) != null && !father.isBlack()) {
            grandFather = father.getParent();
            if (grandFather.getLeft() == father) {
                RBN uncle = grandFather.getRight();
                if (uncle != null && !uncle.isBlack()) {
                    setBlack(father);
                    setBlack(uncle);
                    setRed(grandFather);
                    node = grandFather;
                    continue;
                }
                if (node == father.getRight()) {
                    leftRotate(father);
                    RBN tmp = node;
                    node = father;
                    father = tmp;
                }
                setBlack(father);
                setRed(grandFather);
                rightRotate(grandFather);
            } else {
                RBN uncle = grandFather.getLeft();
                if (uncle != null && uncle.isBlack() == false) {
                    setBlack(father);
                    setBlack(uncle);
                    setRed(grandFather);
                    node = grandFather;
                    continue;
                }
                if (node == father.getLeft()) {
                    rightRotate(father);
                    RBN tmp = node;
                    node = father;
                    father = tmp;
                }
                setBlack(father);
                setRed(grandFather);
                leftRotate(grandFather);
            }
        }
        setBlack(root);
    }

    private void leftRotate(RBN node) {
        RBN right = node.getRight();
        RBN parent = node.getParent();
        if (parent == null) {
            root = right;
            right.setParent(null);
        } else {
            if (parent.getLeft() != null && parent.getLeft() == node) {
                parent.setLeft(right);
            } else {
                parent.setRight(right);
            }
            right.setParent(parent);
        }
        node.setParent(right);
        node.setRight(right.getLeft());
        if (right.getLeft() != null) {
            right.getLeft().setParent(node);
        }
        right.setLeft(node);
    }

    private void rightRotate(RBN node) {
        RBN left = node.getLeft();
        RBN parent = node.getParent();
        if (parent == null) {
            root = left;
            left.setParent(null);
        } else {
            if (parent.getLeft() != null && parent.getLeft() == node) {
                parent.setLeft(left);
            } else {
                parent.setRight(left);
            }
            left.setParent(parent);
        }
        node.setParent(left);
        node.setLeft(left.getRight());
        if (left.getRight() != null) {
            left.getRight().setParent(node);
        }
        left.setRight(node);
    }

    private void setBlack(RBN node) {
        node.setBlack(true);
    }

    private void setRed(RBN node) {
        node.setBlack(false);
    }
}
